#leetcode题目53：最大子数组和
#难度：中等
#时间复杂度：O(n)
#空间复杂度：O(1)
#方法：动态规划

from typing import List


class Solution:
    def maxSubArray(self, nums: List[int]) -> int:
        n=len(nums)
        dp=[0]*n
        dp[0]=nums[0]

        for i in range(1,n):
            dp[i]=max(nums[i],dp[i-1]+nums[i])
        return max(dp)


#测试数据
nums=[-2,1,-3,4,-1,2,1,-5,4]
#预期输出：6
solution=Solution()
print(solution.maxSubArray(nums))

nums=[1]
#预期输出：1
solution=Solution()
print(solution.maxSubArray(nums))

nums=[5,4,-1,7,8]
#预期输出：23
solution=Solution()
print(solution.maxSubArray(nums))


